可拆分有调整时间的平行机排序问题的一个算法

考虑有独立调整时间的同型号平行机排序问题,极小化最迟完工时间,产品允许拆分,同一产品被拆分后各部分可以在不同机器上同时加工,该问题是ＮＰ－ｈａｒｄ问题。本文首先给出该问题的一个启发式算法ＭＬ,然后证明了其最坏情况估计不超过７／４－１／ｍ（ｍ≥２）。     

A fire field model implemented in a parallel computing environment

This paper describes the implementation of a fire field model in the parallel computing environment offered by multiple transputers. The fire model is built into the general purpose SIMPLE-based CFD code HARWELL-FLOW3D. The technique of domain decomposition has been applied tb convert the conventional serial version of FLOW3D into a code capable of efficiently utilizing an arbitrary number of transputers. Fire simulations consisting of up to 24 000 computational cells are performed on parallel systems with up to 15-processors. The run time for this simulation has been reduced from over 4 days on a single processor to just over 8 h on the 15-processor system. An interactive graphics system has also been developed which runs in parallel with the main computations.     

On parallel asynchronous high-order solutions of parabolic PDEs

In achieving significant speed-up on parallel machines, a major obstacle is the overhead associated with synchronizing the concurrent processes. This paper presents high-orderparallel asynchronous schemes, which are schemes that are specifically designed to minimize the associated synchronization overhead of a parallel machine in solving parabolic PDEs. They are asynchronous in the sense that each processor is allowed to advance at its own speed. Thus, these schemes are suitable for single (or multi) user shared memory or (message passing) MIMD multiprocessors. Our approach is demonstrated for the solution of the multidimensional heat equation, of which we present a spatial second-order Parametric Asynchronous Finite-Difference (PAFD) scheme. The well-known synchronous schemes are obtained as its special cases. This is a generalization and expansion of the results in [5] and [7]. The consistency, stability and convergence of this scheme are investigated in detail. Numerical tests show that although PAFD provides the desired order of accuracy, its efficiency is inadequate when performed on each grid point.In an alternative approach that uses domain decomposition, the problem domain is divided among the processors. Each processor computes its subdomain mostly independently, while the PAFD scheme provides the solutions at the subdomains' boundaries. We use high-order finite-difference implicit scheme within each subdomain and determine the values at subdomains' boundaries by the PAFD scheme. Moreover, in order to allow larger time-step, we use remote neighbors' values rather than those of the immediate neighbors. Numerical tests show that this approach provides high efficiency and in the case which uses remote neighbors' values an almost linear speedup is achieved. Schemes similar to the PAFD can be developed for other types of equations [3].This research was supported by the fund for promotion of research at the Technion.     

Thomas rotation and Foucault pendulum under a simple unifying geometrical point of view

In this paper we show that there is a complete parallelism between the Foucault pendulum and the Thomas rotation phenomena by using the concept of parallel transport in a surface. In the case of the Foucault pendulum the surface is the ordinary sphere corresponding to the Earth sphere, whereas in the case of the Thomas rotation the surface is the pseudosphere corresponding to the space of relativistic velocities. Moreover, in both cases we use a simple method that reduces the problem to the parallel transport in a conical surface, and so, to the plane.     

Optimal production scheduling for the dairy industry

The increasing variety of products offered by the food industry has helped the industry to respond to market trends, but at the same time has resulted in a more complex production process, which requires flexibility and an efficient coordination of existing resources. Especially in industrial yogurt production, there is a wide variety of products that differ in features like fat content, the whey used to produce the mixture, the flavor, the size of the container or the language on the label. The great diversification and the special features that characterize yogurt production lines (satisfaction of multiple due dates, variable processing times, sequence-dependent setup times and costs and monitoring of inventory levels), render generic scheduling methodologies impractical for real-world applications. In this work we present a customized Mixed Integer Linear Programming (MILP) model for optimizing yogurt packaging lines that consist of multiple parallel machines. The model is characterized by parsimony in the utilization of binary variables and necessitates the use of only a small pre-determined number of time periods. The efficiency of the proposed model is illustrated through its application to the yogurt production plant of a leading dairy product manufacturing company in Greece.     

NMR analysis of multiple samples using parallel coils: improved performance using reference deconvolution and multidimensional methods

Improvements in the Multiplex Sample NMR method are investigated to explore its capabilities of analyzing multiple samples simultaneously. Issues of quantitation and resolution in the multiple-coil probe are examined in one- and two-dimensional experiments. Improvements in quantitation are shown to result from the use of reference deconvolution for one-dimensional experiments, while the use of two-dimensional methods has much improved resolution and shows the potential for significantly increased parallelism. A multiplicative scheme is shown to be an easily implemented, effective method for generating individual sub-spectra from individual samples.     

A Parallel 3D Unsteady Flow Analysis in an Asymmetrically Constricted Vessel

In this study, parallel computation of unsteady incompressible flow in an asymmetrically constricted 3D vessel has been presented. A time accurate cell centered finite volume method (FVM) in conjunction with pseudo-compressibility technique and Roe's flux difference splitting of nonlinear terms has been employed for solving the Navier-Stokes (NS) equations on the multiple instruction multiple data (MIMD) machine VPP700. The influence of Reynolds' number ( Re ) and the Strouhal number ( St ) on flow dynamic factors like wall pressure (WP), wall shear stress (WSS), central axis velocity (CAV), etc., have been analyzed. Three-dimensional (3D) features in the formation and detachment of separation zones, which are sensitive to both Re and St have been noticed on the diverging wall of the constriction.     

Unbounded parallel batch scheduling with job delivery to minimize makespan

We consider unbounded parallel batch scheduling with job delivery to minimize makespan. When the jobs have identical size, we provide a polynomial-time algorithm. When the jobs have non-identical sizes, we provide a heuristic with a worst-case performance ratio 7/4.